///
/// @file   DoubleLinkedList.h
/// @author xfyxfy <xfyxfy@xfyxfy-VirtualBox>
/// @date   Sat Oct  1 22:36:17 2022
/// 
/// @brief  Include the declaration and implementation of all template classes
/// 
/// 
///
#ifndef _DOUBLELINKEDLIST_H_
#define _DOUBLELINKEDLIST_H_

#include<iostream>

/// exception handling class
class IteratorOutOfBoundsException
{
public:
    IteratorOutOfBoundsException()
	{
	    std::cerr<<"iterator out of bounds exception"<<std::endl;
	}

};
class IteratorMismatchException
{
public:
    IteratorMismatchException()
	{
	    std::cerr<<"iterator mismatch exception"<<std::endl;
	}
};

template<typename Object>
class DoubleLinkedList
{
private:
/// nested doublelinkedlist node
 struct Node			
  {
      Object data;
      Node * prev;		///< point to previous node
      Node * next;		///< point to next node

      Node(const Object &d=Object{ },Node *p=nullptr,Node *n=nullptr)
	  :data{d},prev{p},next{n}{}
      Node(const Object &&d,Node *p=nullptr,Node *n=nullptr)
	  :data{std::move(d)},prev{p},next{n}{}
  };
    
public:
    class const_iterator
    {
    public:
/// default constructor
	const_iterator():theList{nullptr},current{nullptr}{} 
	
	const Object & operator*()const
	    {return retrieve();}

	const_iterator & operator++()
	    {
		current =current->next;
		return *this;
	    }

/// the int parameter is never used
/// distinguished prefix form and postfix form
/// itr++ calls one-parameter operator++
	const_iterator & operator++(int)
	    {
		const_iterator old =*this;
		++(*this);
		return old;
	    }

	bool operator==(const const_iterator &rhs)const
	    {return current==rhs.current; }
	bool operator!=(const const_iterator &rhs)const
	    {return !(*this==rhs);}

    protected:
/// theList is used to make sure
/// iterator is for the correct list
	DoubleLinkedList<Object> *theList;
	Node *current;

	Object &retrieve()const
	    {return current->data;}

/// parametric constructor 
	const_iterator(DoubleLinkedList<Object> &lst,Node *p):theList{&lst},current{p}{}
/// determine whether the iterator is initialized
	void assertIsValid()const 
	    {
		if(theList==nullptr||current==nullptr||current==theList->head)
		    throw IteratorOutOfBoundsException{};
	    }

/// grants the DoubleLinkedList class access 
/// to const_iterator's protected members.
	friend class DoubleLinkedList<Object>;
    };
/// use inheritance to avoid much of the syntactical baggage
    class iterator :public const_iterator
    {
    public:
/// default constructor calls the base-class default constructor 
	iterator(){}

/// the return type is different from const_iterator
/// so it is neccessary  to rewrite these operator	
	Object & operator*()
	    {return const_iterator::retrieve();}
	const Object & operator*()const
	    {return const_iterator::operator*();}

	iterator operator++()
	    {
		this->current=this->current->next;
		return *this;
	    }
	iterator operator++(int)
	    {
		iterator old=*this;
		++(*this);
		return old;
	    }
    protected:
/// the const_iterator's member properties is private thus
/// calls const_iterator's parametric constructor in parameter list
	iterator(DoubleLinkedList<Object> &lst,Node *p):const_iterator{lst,p}{}

	friend class DoubleLinkedList<Object>;
    };
    
public:
    DoubleLinkedList()
	{init();}
/// copy constructor
    DoubleLinkedList(const DoubleLinkedList &rhs)
	{
	    init();
	    for(auto &x: rhs)
		push_back(x);
	}
/// move constructor
    DoubleLinkedList(DoubleLinkedList &&rhs):theSize{rhs.theSize},head{rhs.head},tail{rhs.tail}
	{
	    rhs.theSize=0;
	    rhs.head==nullptr;
	    rhs.tail=nullptr;
       }
    ~DoubleLinkedList()
	{
	    clear();
	    delete head;
	    delete tail;
	}
    DoubleLinkedList & operator=(const DoubleLinkedList & rhs)
	{
	    DoubleLinkedList copy=rhs;///<this '=' calls copy constructor
	    std::swap(*this,copy);
	    return *this;
	}
    DoubleLinkedList & operator=(DoubleLinkedList && rhs)
	{
	    std::swap(theSize,rhs.theSize);
	    std::swap(head,rhs.head);
	    std::swap(tail,rhs.tail);
	    return *this;
	}
/// create an empty DoubleLinkedList
    void init()
	{
	    theSize=0;
	    head=new Node;
	    tail=new Node;
	    head->next=tail;
	    tail->prev=head;
	}

/// *this represents the DoubleLinkedList itself
/// return iterator representing begining and endmarker of the list
    iterator begin()
    	{return {*this,head->next};}
    const_iterator begin()const
        {return {*this,head->next};}
    iterator end()
	{return {*this,tail};}
    const_iterator end()const
	{return {*this,tail};}

    int size()const
	{return theSize;}
    bool empty()const
	{ return size()==0;}

    void clear()
	{
	    while(!empty())
		pop_front();
	}
/// provides access and operation to the front and back of the list
    Object &front()
	{return *begin();}
    const Object &front()const
	{return *begin();}
    Object &back()
	{return *--end();}
    const Object &back()const
	{return *--end();}
    void push_front(const Object & x)
	{insert(begin(),x);}
    void push_front(Object && x)
	{insert(begin(),std::move(x));}
    void push_back(const Object & x)
	{insert(end(),x);}
    void push_back(Object && x)
	{insert(end(),std::move(x));}
    void pop_front()
	{erase(begin());}
    void pop_back()
	{erase(--end());}

///insert x before itr
    iterator insert(iterator itr,const Object &x)
	{
	    itr.assertIsValid();
	    if(itr.theList!=this)
		throw IteratorMismatchException{};
	    
	    Node *p=itr.current;
	    theSize++;
	    return {*this,p->prev=p->prev->next=new Node{x,p->prev,p}};
	}
    iterator insert(iterator itr,Object &&x)
	{
	     itr.assertIsValid();
	    if(itr.theList!=this)
	        throw IteratorMismatchException{};
	    
	    Node *p=itr.current;
	    theSize++;
	    return {*this,p->prev=p->prev->next=new Node{std::move(x),p->prev,p}};
	}

///erase item at itr
    iterator erase(iterator itr)
	{
	     itr.assertIsValid();
	    if(itr.theList!=this)
	        throw IteratorMismatchException{};
	    else if(itr==this->end())
		throw IteratorOutOfBoundsException{};
	    
	    Node *p=itr.current;
	    iterator retVal{*this,p->next};
	    p->prev->next=p->next;
	    p->next->prev=p->prev;
	    delete p;
	    theSize--;
	    return retVal;
	}
///erase item from itrfrom to itrto
    iterator erase(iterator itrfrom,iterator itrto)
	{
	    itrfrom.assertIsValid();
	    itrto.assertIsValid();
	    if(itrfrom.theList!=this || itrto.theList!=this)
	        throw IteratorMismatchException{};
///make sure itrfrom is in front of itrto
	    if(itrto!=this->end())
	    {
		int flag=0;
		for(iterator itr=itrfrom;itr!=end();++itr)
		{
		    if(itr==itrto)
			flag=1;
		}
		if(!flag)
		    throw IteratorOutOfBoundsException{};
	    }
	    
	    for(iterator itr=itrfrom;itr!=itrto;)
		itr=erase(itr);
	    return itrto;
	}
private:
    int theSize;
    Node *head;
    Node *tail;

public:
/// traverse through the list to find whether the _val is in the _list
/// if it is found,return its iterator,otherwise return iterator representing endmarker of the list
    iterator find(DoubleLinkedList<Object>& _list , const Object& _val)const
{
    for(iterator itr=_list.begin();itr !=_list.end();++itr)
    {
	if(*itr==_val)
	    return itr;
    }
    std::cout <<"没有找到" <<_val<<std::endl;
    return _list.end();
}
    iterator find(DoubleLinkedList <Object>& _list , Object&& _val)const
{
    for(iterator itr=_list.begin();itr !=_list.end();++itr)
    {
	if(*itr==std::move(_val))
	    return itr;
    }
    std::cout <<"没有找到" <<_val<<std::endl;
    return _list.end();
}
};

#endif
